Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
LinkedIn Medium
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Remove Nth Node From End of List

Problem Statement

Given a linked list, remove the last nth node from the end of the list and return the head of the modified list.

Example 1:

  • Input: list = 1 -> 2 -> 3 -> 4 -> 5, n = 2
  • Expected Output: 1 -> 2 -> 3 -> 5
  • Justification: The 2nd node from the end is "4", so after removing it, the list becomes [1,2,3,5].

Example 2:

  • Input: list = 10 -> 20 -> 30 -> 40, n = 4
  • Expected Output: 20 -> 30 -> 40
  • Justification: The 4th node from the end is "10", so after removing it, the list becomes [20,30,40].

Example 3:

  • Input: list = 7 -> 14 -> 21 -> 28 -> 35, n = 3
  • Expected Output: 7 -> 14 -> 28 -> 35
  • Justification: The 3rd node from the end is "21", so after removing it, the list becomes [7,14,28,35].

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Solution

  • Two-Pass Approach:

    • Begin by calculating the length of the linked list. This can be done by traversing the list from the head to the end.
    • Once the length is determined, calculate which node to remove by subtracting n from the length.
    • Traverse the list again and remove the node at the calculated position.
  • One-Pass Approach using Two Pointers:

    • Use two pointers, first and second, and place them at the start of the list.
    • Move the first pointer n nodes ahead in the list.
    • Now, move both first and second pointers one step at a time until the first pointer reaches the end of the list. The second pointer will now be n nodes from the end.
    • Remove the node next to the second pointer.
  • Advantage of One-Pass Approach:

    • The one-pass approach is more efficient as it traverses the list only once, whereas the two-pass approach requires two traversals.
  • Edge Cases:

    • If n is equal to the length of the list, remove the head of the list.

Algorithm Walkthrough

Using the input list = [1,2,3,4,5], n = 2:

  1. Initialize two pointers, first and second, at the head of the list.
  2. Move the first pointer 2 nodes ahead. Now, first points to "3" and second points to "1".
  3. Move both first and second pointers one step at a time. When first reaches "5", second will be at "3".
  4. The next node to second is "4", which is the node to be removed.
  5. Remove "4" by updating the next pointer of "3" to point to "5".
  6. The modified list is [1,2,3,5].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: O(L) - We traverse the list with two pointers. Here, L is the number of nodes in the list.
  • Space Complexity: O(1) - We only used constant extra space.
Remove Nth Node From End of List (Medium)
House Robber II (medium)
Mark as Completed

On this page

Problem Statement

Solution

Algorithm Walkthrough

Code

Complexity Analysis